import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/31 9:22
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode t1 = new TreeNode(1, new TreeNode(1), null), t2 = new TreeNode(1);
        System.out.println(solution.isSubtree(t1, t2));
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return dfs(root, subRoot);
    }
    public boolean dfs(TreeNode s, TreeNode t) {
        if (s == null) {
            return false;
        }
        return check(s, t) || dfs(s.left, t) || dfs(s.right, t);
    }

    /**
     *  check为了检查每一次进入时根节点是否相同，根节点不同，那么就s.left 或 s.right匹配 t, 相同，那么开始检查两棵树左右是否相匹配
     * @param s root
     * @param t subRoot
     * @return true / false
     */
    public boolean check(TreeNode s, TreeNode t) {
        if (s == null && t == null) {
            return true;
        }
        if (s == null || t == null || s.val != t.val) {
            return false;
        }
        return check(s.left, t.left) && check(s.right, t.right);
    }
}
